package P783_二叉搜索树节点最小距离;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    int minDiff = Integer.MAX_VALUE;

    //注意，是任意两个节点的最小差值
    //二叉搜索树，左侧的都是小的，右侧的是大的，最小差值在于 左侧最大的，右侧最小的和root这三个节点比较
    public int minDiffInBST(TreeNode root) {
        if (root == null) {
            return minDiff;
        }
        int rightMin = find(root.right, false);
        int leftMax = find(root.left, true);
        if(root.left != null){
            minDiff = Math.min(root.val - leftMax, minDiff);
        }
        if(root.right != null){
            minDiff = Math.min(rightMin - root.val, minDiff);
        }
        return minDiff;
    }

    //左侧找最大，右侧找最小
    //TODO 更好的方法，就是中序遍历就行，因为差值最小的必须就是中序遍历中相邻的两个节点
    public int find(TreeNode root, boolean findMax) {
        if (root == null) {
            return findMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
        int ret = root.val;
        //子问题，找最大最小的时候，顺带也比对一下子node的最小数差
        int rightMin = find(root.right, false);
        int leftMax = find(root.left, true);
        if(root.left != null){
            minDiff = Math.min(root.val - leftMax, minDiff);
        }
        if(root.right != null){
            minDiff = Math.min(rightMin - root.val, minDiff);
        }

        if (findMax) {
            int rightMax = find(root.right, true);
            ret = root.left != null ? Math.max(ret,leftMax) : ret;
            return Math.max(ret, rightMax);
        } else {
            int leftMin = find(root.left, false);
            ret = root.right != null ? Math.min(ret, rightMin) : ret;
            return Math.min(ret, leftMin);
        }
    }

    public static void main(String args[]) {
        TreeNode node90 = new TreeNode(90);
        TreeNode node69 = new TreeNode(69);
        TreeNode node49 = new TreeNode(49);
        TreeNode node89 = new TreeNode(89);
        TreeNode node52 = new TreeNode(52);
        node90.left = node69;
        node69.left = node49;
        node69.right= node89;
        node49.right = node52;
        System.out.println(new P783_二叉搜索树节点最小距离.Solution().minDiffInBST(node90));
    }
}
